// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package flate

import "math"

// 该编码算法将速度置于输出大小之上，是基于Snappy的LZ77风格编码器：github的
// 算法。com/golang/snappy 

const (
	tableBits  = 14             // 表中使用的位。
	tableSize  = 1 << tableBits // 桌子的大小。
	tableMask  = tableSize - 1  // 表索引的掩码。冗余，但可以消除边界检查。
	tableShift = 32 - tableBits // 右移以获取uint32的表位最高有效位。

	// 达到此值时重置缓冲区偏移量。
	// 块之间的偏移量存储为int32值。
	// 由于我们要检查的偏移量是在缓冲区的开始处，我们需要减去当前值并输入
	// 缓冲区，以避免int32溢出。
	bufferReset = math.MaxInt32 - maxStoreBlockSize*2
)

func load32(b []byte, i int32) uint32 {
	b = b[i : i+4 : len(b)] // 帮助编译器消除下一行的边界检查。
	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
}

func load64(b []byte, i int32) uint64 {
	b = b[i : i+8 : len(b)] // 帮助编译器消除下一行的边界检查。
	return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
		uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
}

func hash(u uint32) uint32 {
	return (u * 0x1e35a7bd) >> tableShift
}

// 这些常量是由Snappy实现定义的，因此其
// 程序集实现可以一次快速路径一些16字节的副本。它们
// 在纯Go实现中是不必要的，因为我们不使用相同的
// 优化，但使用相同的阈值并不会带来真正的伤害。
const (
	inputMargin            = 16 - 1
	minNonLiteralBlockSize = 1 + 1 + inputMargin
)

type tableEntry struct {
	val    uint32 // 目标处的值
	offset int32
}

// deflateFast维护表中的匹配项、
// 和上一个字节块以进行跨块匹配。
type deflateFast struct {
	table [tableSize]tableEntry
	prev  []byte // 上一个块，未知时长度为零。
	cur   int32  // 当前匹配偏移量。
}

func newDeflateFast() *deflateFast {
	return &deflateFast{cur: maxStoreBlockSize, prev: make([]byte, 0, maxStoreBlockSize)}
}

// encode对src中给定的块进行编码，并将标记
// 附加到dst并返回结果。
func (e *deflateFast) encode(dst []token, src []byte) []token {
	// 确保e.cur不被包装。
	if e.cur >= bufferReset {
		e.shiftOffsets()
	}

	// 此检查不在Snappy实现中，但在那里，调用方
	// 而不是被调用方处理此情况。
	if len(src) < minNonLiteralBlockSize {
		e.cur += maxStoreBlockSize
		e.prev = e.prev[:0]
		return emitLiteral(dst, src)
	}

	// slim何时停止寻找偏移/长度副本。inputMargin 
	// 允许我们在主循环中使用emitLiteral的快速路径，同时我们正在
	// 寻找副本。
	sLimit := int32(len(src) - inputMargin)

	// nextEmit是src中下一个emitLiteral的起始位置。从C++快照实现中复制的
	nextEmit := int32(0)
	s := int32(0)
	cv := load32(src, s)
	nextHash := hash(cv)

	for {
		// 扫描（或跳过），请每三个字节查看一次，以此类推。。当找到匹配的
		// 时，立即返回查看每个字节。这是一个小损失（~5%的性能，~0.1%的密度）对于可压缩的数据来说是因为更多的簿记，但是对于不可压缩的数据（例如
		// JPEG），这是一个巨大的胜利，因为压缩器很快“意识到”
		// 数据是不可压缩的，并且不需要到处寻找匹配的
		// 数据。
		// 
		// “skip”变量跟踪自上次匹配以来有多少字节；将其除以32（即右移5）得到
		// 每次迭代需要向前移动的字节数。
		skip := int32(32)

		nextS := s
		var candidate tableEntry
		for {
			s = nextS
			bytesBetweenHashLookups := skip >> 5
			nextS = s + bytesBetweenHashLookups
			skip += bytesBetweenHashLookups
			if nextS > sLimit {
				goto emitRemainder
			}
			candidate = e.table[nextHash&tableMask]
			now := load32(src, nextS)
			e.table[nextHash&tableMask] = tableEntry{offset: s + e.cur, val: cv}
			nextHash = hash(now)

			offset := s - (candidate.offset - e.cur)
			if offset > maxMatchOffset || cv != candidate.val {
				// 超出范围或不匹配。
				cv = now
				continue
			}
			break
		}

		// 已找到一个4字节的匹配项。稍后我们将查看
		// 是否超过4个字节匹配。但是，在比赛之前，src[nextEmit:s]是无与伦比的。发出
		// 将它们作为文本字节。
		dst = emitLiteral(dst, src[nextEmit:s])

		// 打电话给emitCopy，然后看看是否有另一个emitCopy可以成为我们的下一个
		// 移动。重复上述步骤，直到我们在
		// 上一次emitCopy调用消耗的内容之后立即找到与输入不匹配的内容。
		// 
		// 如果我们正常退出这个循环，那么我们需要调用emitLiteral next，
		// 尽管我们还不知道这个字面值会有多大。我们通过继续主循环的下一次迭代来处理
		// 。如果我们接近耗尽输入，我们也可以通过goto退出这个循环。
		for {
			// 不变量：我们在s处有一个4字节匹配，不需要在s之前发出任何
			// 文本字节。

			// 尽可能长地扩展4字节匹配。
			// 
			s += 4
			t := candidate.offset - e.cur + 4
			l := e.matchLen(s, t, src)

			// matchToken是flate的等效于Snappy的emitCopy。（长度，偏移量）
			dst = append(dst, matchToken(uint32(l+4-baseMatchLength), uint32(s-t-baseMatchOffset)))
			s += l
			nextEmit = s
			if s >= sLimit {
				goto emitRemainder
			}

			// 我们现在可以立即从s开始工作，但为了改进
			// 压缩，我们首先更新s-1和s处的哈希表。如果
			// 下一步不是另一个emitCopy，也要计算nextHash 
			// 在s+1。至少在GOARCH=amd64上，这三个hash计算
			// 比
			// 三个load32调用更快，只需一个load64调用（带一些移位）。
			x := load64(src, s-1)
			prevHash := hash(uint32(x))
			e.table[prevHash&tableMask] = tableEntry{offset: e.cur + s - 1, val: uint32(x)}
			x >>= 8
			currHash := hash(uint32(x))
			candidate = e.table[currHash&tableMask]
			e.table[currHash&tableMask] = tableEntry{offset: e.cur + s, val: uint32(x)}

			offset := s - (candidate.offset - e.cur)
			if offset > maxMatchOffset || uint32(x) != candidate.val {
				cv = uint32(x >> 8)
				nextHash = hash(cv)
				s++
				break
			}
		}
	}

emitRemainder:
	if int(nextEmit) < len(src) {
		dst = emitLiteral(dst, src[nextEmit:])
	}
	e.cur += int32(len(src))
	e.prev = e.prev[:len(src)]
	copy(e.prev, src)
	return dst
}

func emitLiteral(dst []token, lit []byte) []token {
	for _, v := range lit {
		dst = append(dst, literalToken(uint32(v)))
	}
	return dst
}

// matchLen返回src[s:]和src[t:]之间的匹配长度。
// t可以为负值，表示比赛从e.prev开始。
// 我们假设src[s-4:s]和src[t-4:t]已经匹配。
func (e *deflateFast) matchLen(s, t int32, src []byte) int32 {
	s1 := int(s) + maxMatchLength - 4
	if s1 > len(src) {
		s1 = len(src)
	}

	// 如果我们在当前区块内
	if t >= 0 {
		b := src[t:]
		a := src[s:s1]
		b = b[:len(a)]
		// 将匹配时间延长到尽可能长。
		for i := range a {
			if a[i] != b[i] {
				return int32(i)
			}
		}
		return int32(len(a))
	}

	// 我们在上一个区块中找到了一个匹配项。
	tp := int32(len(e.prev)) + t
	if tp < 0 {
		return 0
	}

	// 尽可能延长比赛时间。
	a := src[s:s1]
	b := e.prev[tp:]
	if len(b) > len(a) {
		b = b[:len(a)]
	}
	a = a[:len(b)]
	for i := range b {
		if a[i] != b[i] {
			return int32(i)
		}
	}

	// 如果我们达到了极限，我们将匹配上一个区块允许的所有内容，然后返回。
	n := int32(len(b))
	if int(s+n) == s1 {
		return n
	}

	// 继续在当前块中查找更多匹配项。
	a = src[s+n : s1]
	b = src[:len(a)]
	for i := range a {
		if a[i] != b[i] {
			return int32(i) + n
		}
	}
	return int32(len(a)) + n
}

// 重置重置编码历史记录。
// 这可以确保不匹配上一个块。
func (e *deflateFast) reset() {
	e.prev = e.prev[:0]
	// 调整偏移量，因此所有匹配项都将无法通过距离检查。
	// 表中不应>=e.cur。
	e.cur += maxMatchOffset

	// 防止e.cur包围。
	if e.cur >= bufferReset {
		e.shiftOffsets()
	}
}

// shiftofset将向下移动所有匹配偏移量。
// 只有在极少数情况下才调用此函数，以防止整数溢出。
// 参见https:
func (e *deflateFast) shiftOffsets() {
	if len(e.prev) == 0 {
		for i := range e.table[:] {
			e.table[i] = tableEntry{}
		}
		e.cur = maxMatchOffset + 1
		return
	}

	// 把桌上所有不太远的东西都放下。
	for i := range e.table[:] {
		v := e.table[i].offset - e.cur + maxMatchOffset + 1
		if v < 0 {
			// 我们想将e.cur重置为maxMatchOffset+1，所以我们需要将
			// 所有表项向下移动（e.cur-（maxMatchOffset+1））。
			// 因为我们忽略了matches>maxMatchOffset，所以我们可以将任何负偏移量限制为0。
			v = 0
		}
		e.table[i].offset = v
	}
	e.cur = maxMatchOffset + 1
}
